<!DOCTYPE html>
<html>
	<head>
		<meta charset="UTF-8">
		<title></title>
	</head>
	<body>
		<!--堆排序
		解析:
			堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
			堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：
			即子结点的键值或索引总是小于（或者大于）它的父节点。-->
		<script type="text/javascript">
			function heapSort(array) {
				console.time('堆排序耗时');
				if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
					var heapSize = array.length,temp; // 建堆
					for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
						heapify(array, i, heapSize);
					}
					for (var j = heapSize - 1; j >= 1; j--) { // 堆排序
						temp = array[0];
						array[0] = array[j];
						array[j] = temp;
						heapify(array, 0, --heapSize);
					}
					console.timeEnd('堆排序耗时');
					return array;
				} else{
					return 'array is not Array!';
				}
			}
			
			function heapify(arr, x, len) {
				if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof x === 'number') {
					var l = 2 * x + 1;
						r = 2 * x + 2;
						largest = x,
						temp;
					if (l < len && arr[l] > arr[largest]) {
						largest = 1;
					}
					if (r < len && arr[r] > arr[largest]) {
						largest = r;
					}
					if (largest != x) {
						temp = arr[x];
						arr[x] = arr[largest];
						arr[largest] = temp;
						heapify(arr, largest, len);
					}
				} else{
					return 'arr is not Array or x is not a number!'
				}
			}
			var arr = [91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22];
			document.write(heapSort(arr));
		</script>
	</body>
</html>
